1. Field of the Invention
The present invention relates to method of and apparatus for generating a variable length code table for use with a variable length code table generating apparatus which generates a variable length code table used to generate a variable length code.
2. Description of the Prior Art
Digital VTRs (video tape recorders) that have been developed recently compress digital data (digital video and audio signals) when recording the same on a magnetic tape and expand the digital data when reproducing the same from the magnetic tape.
FIG. 1 of the accompanying drawings shows an example of a digital VTR of the type that digital data is compressed when it is recorded on a magnetic tape and that digital data is expanded when it is reproduced from the magnetic tape.
As shown in FIG. 1, in the video signal processing system of the digital VTR, a recording digital video signal is supplied to an input terminal 1 and then shuffled by a shuffling circuit 2 at every block of 4 pixels.times.4 pixels. Video data thus shuffled by the shuffling circuit 2 is supplied to and transformed by a DCT (discrete cosine transform) circuit 3 at the unit of blocks into coefficient data ranging from a DC component to a high-order AC component.
FIG. 2 shows an example of the coefficient data thus transformed. As shown in FIG. 2, the coefficient data thus transformed is comprised of coefficient data DC Y of DC component luminance signal, coefficient data DC C(R-Y, B-Y) of DC component color signal, coefficient data AC1 Y of AC component luminance signal, coefficient data AC1 C(R-Y, B-Y) of AC component color signal, . . . coefficient data AC15 Y of AC component luminance signal and coefficient data AC15 C(R-Y, B-Y) of AC component color signal.
The above-mentioned coefficient data from the DCT circuit 3 are supplied to a quantization controller 4 which determines quantizaion index such that 10 blocks of a luminance signal Y and 5 blocks of each of color difference signals R-Y, B-Y of the coefficient data (shown in FIG. 2) supplied thereto fall within a block (i.e., so-called sync. block) recorded on a magnetic tape 17. A step size, which will be described later on, is obtained on the basis of the quantization index, and coefficient data is quantized by the step size obtained from the quantization index. Therefore, the coefficient data from the quantization controller 4 are supplied to a quantizer 5, in which they are quantized on the basis of the step size obtained from the quantization index.
The coefficient data quantized by the quantizer 5 are supplied to a VLC (variable length code) encoder 6. The VLC encoder 6 encodes the coefficient data supplied thereto to provide variable length coded quantized coefficient data by using an entropy code. The quantized coefficient data thus processed by the VLC encoder 6 are temporarily stored and rearranged at every sync. block by a buffer memory 7. The data from the buffer memory 7 are supplied to an outer code circuit 8, in which they are added with an outer code parity and then supplied to a mixer 12.
On the other hand, in the audio signal processing system of the digital VTR, a recording digital audio signal is supplied to an input terminal 9. The digital audio signal supplied to the input terminal 9 is shuffled by a shuffling circuit 10, and the audio data thus shuffled by the shuffling circuit 10 is added with an outer code parity by an outer code circuit 11. Then, the audio data processed by the outer code circuit 11 is supplied to the mixer 12.
The mixer 12 mixes the video data supplied thereto from the outer code circuit 8 and the audio data supplied thereto from the outer code circuit 11 to provide mixed data. The mixed data from the mixer 12 is supplied to an inner code circuit 13, in which it is added with an inner code parity and supplied to a channel encoder 14. Data channel-encoded by the channel encoder 14 is supplied through a recording amplifier 15 to a magnetic head 16, thereby being recorded on the magnetic tape 17 so as to form slant tracks.
Processing in the VLC encoder 6 will be described. The DCT circuit 3 transforms the input data into the coefficient data ranging from DC component to the high-order AC component as earlier noted with reference to FIG. 2. The DCT circuit 3 scans coefficient data in a zigzag fashion as shown in FIG. 3. FIG. 3 shows the case that the coefficient data are scanned from DC component coefficient data DC to high-order AC component coefficient data AC33.
The VLC encoder 6 shown in FIG. 1 encodes the DC component coefficient data DC of the zigzag-scanned coefficient data to provide a fixed length code. The VLC encoder 6 encodes AC component coefficient data AC1 through AC15 (AC01 through AC33 in the example shown in FIG. 3) to provide variable length codes.
Processing for encoding the AC component coefficient data AC1 through AC15 into variable length codes will be described with reference to a flowchart of FIG. 4.
Referring to FIG. 4, following the start of operation, sizes of coefficient data are calculated in step S1. Sizes of coefficient data are calculated on the basis of a table (shown in FIG. 5) which is used to obtain sizes of coefficient data. The table shown in FIG. 5 indicates numerical values representing values of coefficient data on the right-hand columns thereof and numerical values representing sizes corresponding to values of coefficient data on the left-hand columns thereof. Then, the processing proceeds to step S2.
In step S2, sizes of coefficient data are coded on the basis of a coefficient table shown in FIG. 6. The coefficient table shown in FIG. 6 is used to obtain codes corresponding to sizes of coefficient data. The table shown in FIG. 6 indicates numerical values representing values of sizes obtained from the table shown in FIG. 5 on the left-hand columns thereof and codes representing codes corresponding to the values of the sizes on the right-hand columns thereof. Then, the processing proceeds to step S3.
In step S3, values of coefficient data are calculated. The value of coefficient data teaches the order in which the value of coefficient data is placed on the right-hand column corresponding to the corresponding size of the table (shown in FIG. 5) which obtains sizes of coefficient data. The minimum value is assumed to be "0" when counted in the values corresponding to the sizes of coefficient data. Then, the processing proceeds to step S4.
In step S4, the values thus obtained are expressed by corresponding bits of large sizes (referred to hereinafter as "(size) bit"), i.e., information representing the sequential order is converted into (size) bit. Then, the processing proceeds to step S5.
In step S5, coefficient data is coded by adding coded size and value of (size) bit. More specifically, the size obtained in accordance with the value of coefficient data on the table shown in FIG. 6 is converted into the code. Then, the (size) bit which results from converting the value indicative of the sequential order of the value of coefficient data in the size area is added to the coded size, thus the variable length code being obtained. Then, the processing returns to step S1, and the variable length coding is repeated similarly as described above.
The variable length coding will be described more fully with reference to FIGS. 5 and 6.
When coefficient data is "-21", a size of the coefficient data "-21" is "5" as shown on the table of FIG. 5. As shown in FIG. 5, the coefficient value corresponding to the size "5" falls in a range of from -31 to -16 and from 16 to 31. Therefore, when the coefficient value "-31" is counted as 0 th coefficient value, the coefficient value "-21" is 10 th coefficient value so that the coefficient data "-21" has a value "10". The code of size "5" is "11110" and the value "10" is expressed as "01010" by (size) bits, i.e., 5 bits. Thus, the variable length code of the coefficient value "-21" is obtained as "1111001010" by adding "11110" and "01010".
When the coefficient data is "5", the size of the coefficient data having the value "5" is "3" as shown in FIG. 5. The coefficient value corresponding to the size "3" falls in a range of from -7 to -4 and from 4 to 7 as shown in FIG. 5. In the column of the size "3", the value of coefficient data having the value "5" is 5 th coefficient value when the coefficient data value "-7" is counted as 0 th coefficient value. Therefore, the coefficient data "5" has a value "5". The code of the size "3" is "110" as shown in FIG. 6, and the value "5" is expressed as "101" by (size) bits, i.e., 3 bits. Thus, the variable length code of the coefficient value " 5" is expressed as "110101" by adding "110" and "101".
In this digital VTR, the total code length obtained when digital data is compressed depends upon the table (shown in FIG. 6) which converts the size into the code. Therefore, not only the VLC encoder 6 shown in FIG. 1 but also the quantization controller 4 includes the table information shown in FIG. 6. Accordingly, the quantization controller 4 determines the quantization index such that data fall within one sync. block. Then, the quantization controller 4 supplies the quantization index to the quantizer 5 as shown in FIG. 1.
Since the quantization index is the immediate cause of a distortion in the data obtained when the data is rearranged, it is very important to determine the above-mentioned table (see FIG. 6) which obtains the code from the size.
Therefore, the table (see FIG. 6) which obtains codes from sizes is generated by the procedure shown in FIG. 7. Processing for generating the table which obtains codes from sizes will be described below with reference to a flowchart of FIG. 7. This table will be referred hereinafter to as "conversion table" for simplicity. Also, let it be assumed that steps of the flowchart of FIG. 7 are not executed by the digital VTR shown in FIG. 1 but by a system which is arranged exclusively. Accordingly, steps of the flowchart of FIG. 7 will be described on the assumption that respective elements which construct the digital VTR shown in FIG. 1 are forming a conversion table generating apparatus.
Referring to FIG. 7, following the start of operation, the processing proceeds to step S10, whereat a proper conversion table is set, i.e., a suitable conversion table is loaded onto the quantization controller 4 shown in FIG. 1. Then, the processing proceeds to step S11.
In step S11, all data are inputted. Inputting all data means that data are inputted at a practical frequency, e.g., video signals of all sorts of patterns are supplied to the input terminal 1 shown in FIG. 1. Then, the processing proceeds to step S12.
In step S12, statistic of data inputted to the VLC encoder 6 shown in FIG. 1 is calculated. In other words, statistic of data outputted from the quantizer 5 shown in FIG. 1, i.e., an incidence probability of sizes obtained by the conversion table shown in FIG. 5 is calculated. Then, the processing proceeds to step S13.
In step S13, a new conversion table is generated by the Huffman code method on the basis of the statistic, i.e., new conversion table is generated by the Huffman code method on the basis of the statistic that was obtained by the output from the quantizer 5 shown in FIG. 1. Then, the processing proceeds to the next decision step S14.
It is determined in decision step S14 whether or not the new conversion table is the same as the former conversion table. If a YES is outputted at decision step S14, then the processing is ended. That is, if the new conversion table is the same as the former conversion table as represented by a YES at decision step S14, it is to be appreciated that the table is converged. Therefore, the new conversion table is determined as the conversion table (shown in FIG. 6) for obtaining the code from the size. If a NO is outputted at decision step S14, then the processing proceeds to step S15.
In step S15, the new conversion table is set, and the processing returns to step S10.
The above-mentioned method of generating conversion tables will be described more fully below. Initially, the quantization index is determined by using a proper conversion table such that data may fall within one sync. block. When the statistic of data quantized by the resultant quantization index is calculated on the basis of the size, the resultant statistic data becomes different from the statistic data obtained before the proper conversion table is used. Therefore, the new conversion table is generated on the new statistic data thus obtained.
The quantization index is determined by using the new conversion table, and the statistic amount of data quantized at that time is calculated. When the statistic amount of data obtained after the new conversion table is generated last and the statistic amount of data quantized by using the new conversion table generated this time are compared with each other, the resultant statistic amount is different. Therefore, a new conversion table is generated on the basis of the resultant statistic amount. If the similar table generating processing is repeated, then new conversion tables thus obtained are converged to a certain table in which the statistic amount obtained when the conversion table is generated and the statistic amount obtained when the processing is carried out by using the table thus generated become coincident with each other. This conversion table is a target conversion table.
The procedure for generating a new conversion table by the Huffman code method as shown at step S13 in the flowchart of FIG. 7 will be described with reference to a flowchart of FIG. 8.
Referring to FIG. 8, following the start of operation, the processing proceeds to step S20, whereat sizes are arranged in the order of large occurrence probability. Then, the processing proceeds to step S21.
In step S21, the minimum occurrence probability and the second minimum occurrence probability are degenerated to produce a new size. The occurrence probability of the new size is represented by a sum of the minimum occurrence probability and the second minimum occurrence probability. A code bit "0" is assigned to the small occurrence probability and a code bit "1" is assigned to the large occurrence probability. Then, the processing proceeds to decision step S22.
It is determined in decision step S22 whether or not only occurrence probability "1" is obtained after step S21 is executed. If a YES is outputted at decision step S22, then the processing is ended. If on the other hand a NO is outputted at decision step S22, then the processing returns to step S20.
According to the above-mentioned processing, the code word of short code length is assigned to a size having large occurrence probability and the cord word of long code length is assigned to a size having small occurrence probability.
The arrangement of variable length code obtained by the Huffman code method will be described with reference to FIG. 9. In this case, let it be assumed that sizes are "0" to "6" and that occurrence probabilities of these sizes "0" to "6" are 0.22, 0.18, 0.17, 0.16, 0.14, 0.09 and 0.04, respectively. In FIG. 9, reference symbols "A0" through "A6" depict step Nos.
As shown in FIG. 9, the initial state is expressed by the step A0. After steps S20 and S21 are executed, the step A0 proceeds to the step A1. Then, the step A1 proceeds to the step A2. After steps A0 to A6 are executed, the occurrence probability becomes "1" and the processing is ended. By way of example, when "1" is assigned to the occurrence probability of 0.09 and "0" is assigned to the occurrence probability of 0.04, a new occurrence probability of "0.13" is obtained in the step A1. In the next step A2, the code bits "1" and "0" are assigned to the occurrence probabilities of 0.17 and 0.16, respectively.
In the next step A3, a new occurrence probability of "0.33" is obtained from the occurrence probabilities of 0.17 and 0.16. In the next step A4, the code bits "1" and "0" are assigned to the occurrence probabilities of 0.22 and 0.18. Then, a new occurrence probability of "0.40" is obtained from the occurrence probabilities of 0.22 and 0.18.
In the next step A5, the code bits "1" and "0" are assigned to occurrence probabilities of 0.33 and 0.27, respectively. Then, a new occurrence probability of "0.60" is obtained from the occurrence probabilities of 0.33 and 0.27. In the next step A6, the code bits "1" and "0" are assigned to occurrence probabilities of 0.60 and 0.40, respectively. Then, a new occurrence probability of "1.00" is obtained from the occurrence probabilities of 0.60 and 0.40.
Therefore, according to this example, a code word "01" is assigned to the size "0", a code word "00" is assigned to the size "1", a code word "111" is assigned to the size "2", a code word "110" is assigned to the size "3", a code word "101" is assigned to the size "4", a code word "1001" is assigned to the size "5", and a code word "1000" is assigned to the size "6".
The size "6" will be described below by way of example. Initially, in the step A1, the code bit "0" is assigned to the occurrence probability of 0.04 of the size "6", and a new occurrence probability of 0.13 is obtained from the occurrence probability of 0.04 of the size "6" and the occurrence probability of 0.09 of the size "5". In the next step A2, the code bit "0" is assigned to the new occurrence probability of 0.13.
Having followed the arrows in FIG. 9, we have occurrence probability of 0.27 in step A4 after occurrence probabilities of 0.27, 0.27 are obtained in steps A2, A3. In the next step A5, the code bit "0" is assigned to the occurrence probability of 0.27. Then, following the arrow, we have occurrence probability of 0.60 in step A6. In step A6, the code bit "1" is assigned to the occurrence probability of 0.60. Accordingly, following the assigned code bits "1", "0", "0", "0" in the opposite direction, we have a code word "1000" that is assigned to the occurrence probability of 0.04 of the size "6".
When tables are generated as described above, the problem is to input and compress data as much as one can consider. In the case of the VTR, for example, the problem is to input incoming image data at the practical frequency. It is, however, almost impossible to generate tables by inputting incoming image data at the practical frequency, i.e., inputting image data of all sorts of patterns.